// 维护一个队列，依然用指针代表节点的状态

const wordBreak = function (s, wordDict) {
  const wordSet = new Set(wordDict);
  const len = s.length;
  const visited = new Array(len);

  let queue = [];
  queue.push(0);

  while (queue.length) {
    const start = queue.shift();
    if (visited[start]) continue;
    visited[start] = true;

    for (let i = start + 1; i <= len; i++) {
      const prefix = s.slice(start, i);
      if (wordSet.has(prefix)) {
        if (i < len) {
          queue.push(i);
        } else {
          return true;
        }
      }
    }
  }
  return false;
};
